package com.misyi.list;

/**
 * 手写ArrayList
 *
 * @author licong
 * @date 2021-09-28 下午11:35
 */
class ArrayList<E> extends AbstractList<E> {

    private E[] elements;

    public ArrayList() {
        this(DEFAULT_CAPACITY);
    }

    public ArrayList(int capacity) {
        if (capacity < DEFAULT_CAPACITY) {
            capacity = DEFAULT_CAPACITY;
        }
        this.elements = (E[]) new Object[capacity];
    }


    /**
     * 查找指定元素在列表中的索引位置
     *
     * @param element 元素
     * @return 在列表中索引位置
     */
    @Override
    public int indexOf(E element) {
        if (element == null) {
            for (int i = 0; i < size; i++) {
                if (elements[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                E e = elements[i];
                if (element.equals(e)) {
                    return i;
                }
            }
        }
        return ELEMENT_NOT_FIND;
    }

    /**
     * 在列表最后面添加指定元素
     *
     * @param element 元素
     */
    @Override
    public void add(E element) {
        ensureCapacity();
        elements[size] = element;
        size++;
    }

    /**
     * 在指定索引位置添加元素
     *
     * @param index   索引位置
     * @param element 元素
     */
    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacity();
        // 由大移动到小
        for (int i = size; i >= index; i--) {
            if (i == index) {
                elements[index] = element;
            } else {
                elements[i] = elements[i - 1];
            }
        }
        size++;

        // 第一种方式, 从小至大, 需要存储旧值, 比较麻烦
//        E old = null;
//        for (int i = index; i <= size; i++) {
//            // 将前一次迭代取出的旧元素存储
//            if (old != null) {
//                elements[i - 1] = old;
//            }
//            // 取出旧元素
//            old = elements[i];
//            // 将原有位置的元素设置新元素
//            elements[i] = element;
//        }
//        size++;
    }

    /**
     * 查找指定索引位置的元素
     *
     * @param index 索引
     * @return 指定索引位置的元素
     */
    @Override
    public E get(int index) {
        rangeCheck(index);
        return elements[index];
    }


    /**
     * 往指定索引位置设置元素
     *
     * @param index   索引
     * @param element 添加的元素
     * @return 原索引位置的元素
     */
    @Override
    public E set(int index, E element) {
        rangeCheck(index);
        E oldElement = elements[index];
        elements[index] = element;
        return oldElement;
    }

    /**
     * 在列表中删除指定索引的元素
     *
     * @param index 索引位置
     * @return 被删除的元素
     */
    @Override
    public E remove(int index) {
        rangeCheck(index);
        E result = elements[index];
        for (int i = index; i < size; i++) {
            elements[i] = elements[i + 1];
        }
        size--;
        return result;
    }

    /**
     * 从此列表中删除第一次出现的指定元素
     *
     * @param element 删除的元素
     * @return 删除操作是否成功
     */
    @Override
    public boolean remove(E element) {
        int index = indexOf(element);
        if (index == ELEMENT_NOT_FIND) {
            return false;
        }
        remove(index);
        return true;
    }

    /**
     * 清空列表
     */
    @Override
    public void clear() {
        size = 0;
    }

    /**
     * 确保容量正常
     */
    private void ensureCapacity() {
        // 数组满时, 进行扩容
        if (elements.length == size) {
            // 以 1.5 倍方式进行扩容
            E[] newElements = (E[]) new Object[size + (size >> 1)];
            for (int i = 0; i < elements.length; i++) {
                newElements[i] = elements[i];
            }
            elements = newElements;
            System.out.println("数组扩容: oldCapacity=" + size + ", newCapacity=" + elements.length);
        }
    }

    @Override
    protected Object node(int index) {
        return get(index);
    }
}
